For many applications, e.g. smart cards for pay TV purposes, credit cards, passports, dongels, military command and control systems, unforgeable systems for access control or digital signature are required. Such access control and signature systems may include public keys. But in many public key identification and access control systems the key management becomes very complicated when the number of users increases. Typical problems are: 1) the memory size of the public directory; 2) interaction with the directory is needed whenever users want to communicate causing simultaneous access problems if the directory is not duplicated; 3) the "blacklisting" of invalid and old keys; 4) adding a new member (e.g. "allusers" update mail to the members); 5) risks of forgery of the public directory (e.g. interchange of public keys between an authorized user and an unauthorized party attempting to gain access). Entities might try to duplicate, playback, or forge key identification devices (hereafter called `identifiers` because they identify authorized users).
A known solution to this problem of digital identification and signature is described in European Patent Applications EP 0252499 and EP 0325238 by Fiat and Shamir. This method utilizes a trusted authority which issues an identifier to each authorized user. No further interaction with any center is required. In particular, no interaction is required for either generating or verifying identities and signatures. An unlimited number of users can join the system without statistically compromising its security. Interactions with identifiers do not allow forgery of identifiers. No user or verifier directories are needed.
Although the known approach disclosed in, for example, EP 0252499 works well in many applications, certain theoretical aspects may result in compromised security. A brief summary of the protocol, i.e. the flow scheme, which is disclosed in EP 0252499 follows. In the following description,
U is an user, e.g. a smart card; PA1 V is a verifier; PA1 k is an integer number, e.g. in the range [1,18]; PA1 r is a random integer number in the range [0,n); PA1 (e.sub.1 e.sub.2 e.sub.3. . . e.sub.k) is a binary vector. PA1 1) prepares a string ID containing information which is unique to the entity U; PA1 2) computes a set of values v.sub.ji =f(ID,j.sub.i) for small values of j.sub.i ; PA1 3) selects k values of the v.sub.ji which are quadratic residues mod n and computes the values s.sub.ji such that s.sub.ji.sup.2 *v.sub.ji =1 mod n; PA1 4) issues an identifier containing ID, j.sub.1,i.sub.2, . . . , j.sub.k,s.sub.j1,s.sub.j2, . . . , s.sub.jk and n. PA1 1) U sends ID and j.sub.1,j.sub.2, . . . , i.sub.k to V; PA1 2) V generates the v.sub.ji by computing v.sub.ji =f(ID,j.sub.i) for i=1,2, . . . , k; PA1 3) U picks a random r and sends r.sup.2 mod n to V; PA1 4) V chooses a binary vector (e.sub.1 e.sub.2 e.sub.3. . . e.sub.k) and sends it to U; PA1 5) U multiplies r by each of the s.sub.ji values where bit ##EQU1## (for example, if the binary vector is 1100100000, then y=r*s.sub.j1 *s.sub.j2 *s.sub.j5 mod n); PA1 V checks that ##EQU2## PA1 U sends ID and j.sub.c,j.sub.c, . . . , j.sub.c to V; PA1 V generates k times the sane v.sub.jc since all the j.sub.i are identical; PA1 U picks a random r and sends r.sup.2 mod n to V; PA1 V chooses a binary vector (e.sub.1 e.sub.2 e.sub.3. . . e.sub.k) and sends it to U; PA1 U sends to V ##EQU3## V checks that ##EQU4## B) This approach is less difficult than "A" above because it is easier mathematically to compute the inverse of one of the v.sub.ji, e.g. v.sub.jc.sup.-1, than it is to compute the inverse root s.sub.jc. If such a value is known then the probability is 0.5 that the above-described known identification system can be compromised as follows: PA1 U sends ID and j.sub.c,j.sub.c, . . . , j.sub.c to V; PA1 V generates k times the same v.sub.jc since all the j.sub.i are identical; PA1 U picks a random r and sends r.sup.2 mod n to V; PA1 V chooses a binary vector (e.sub.1 e.sub.2 e.sub.3. . . e.sub.k) and sends it to U; PA1 U sends to V y=r(v.sub.jc.sup.-1).sup.int (.SIGMA.e.sub.i /2) mod n; PA1 V checks that ##EQU5## PA1 U sends ID and j.sub.c,j.sub.c, . . . , j.sub.c to V; PA1 V generates k times the same v.sub.jc since all the j.sub.i are identical; PA1 U executes the following algorithm: ##EQU6## The probability that such an r will not be discovered decreases exponentially following the law of 2.sup.-.chi.. Typically, the probability that a desired r will be found before x=7, where x is the number of iterations of the WHILE loop, is about 99%. PA1 U sends y together with (e.sub.1 e.sub.2. . . e.sub.k) to V; PA1 V successfully compares ##EQU7## The weakness of the known system resides in the fact that the v.sub.j (j=1,k) values are considered to be k different secret values and, therefore, forging a part of them (here 1/18, k=18), e.g. using the described signature forgery approach, compromises the security of the scheme. PA1 1) The order of ID, PK, and c in G can be permuted. A normalization will appear to be good in practice since the VPKD can be used by all different modulo based algorithms requiring public key transmissions. PA1 2) Public or secret reversible functions for mixing and separating ID, PK and c can be used instead of simple concatenation, e.g. compression, permutation or even recurrent nested VPKD. PA1 3) In schemes requiring k different public key values PK.sub.U1,PK.sub.U2,PK.sub.U3, . . . , PK.sub.UK (for each user U), which can be permuted without compromising the functionality of the scheme (concerning the known identification system where all the v.sub.j play the same role provided that for each s.sub.j.sup.2 v.sub.j =1 mod n), the use of c can be avoided by permuting: ##EQU8## until a G.sub.U,.sub..mu. which is a d-th power mod n is found. The probability that an appropriate G.sub.U, .sub..mu. will not be found is EQU (3/4).sup.18! &lt;1O(.sup.-ex),ex=10.sup.14 PA1 4) Checksums, random "one way" functions, CRCs (cyclic redundancy check) and other mathematical methods can be included in G (e.g. f(ID,PK) where f maps long strings to a few bytes). In systems where a group (or all entities) has the same ID (or no ID at all), ID can be eliminated or replaced by a constant. This may be applicable to pay TV systems in which it is often desirable to address groups of subscribers. PA1 5) ID and/or the PK can be transmitted in a plain or enciphered form along with the corresponding g to improve security. PA1 6) Simple exponentiation of g can be replaced by a polynomial computation. To provide this capability, the authority publishes a sequence of numbers .OMEGA..sub.i and computes g.sub.U in such a way that ##EQU9##
In the known approach, an "authority" chooses a pseudo random function f and a modulus n=pq, where p and q are both prime numbers that are known only to the authority (A=B mod n is equivalent to mod (A,n)=mod (B,n)). To issue an identifier, the authority:
The identity verification protocol between user U and verifier V then proceeds as follows:
The security of the described protocol can be compromised in a number of ways. Three techniques, designated A, B, and C, are described below.
A) If an unauthorized user U attempts to gain access and discovers only one of the s.sub.ji, e.g. s.sub.jc, the system becomes vulnerable to the following scheme in which user U successfully misrepresents himself:
This test will be true if .SIGMA.e.sub.i is even.
If a pay TV verifier is public and available in any desired quantity, an entity attempting to gain unauthorized access could use four verifiers simultaneously to obtain, for example, a TV program descrambled up to 94% by using approach B. If four additional verifiers are added, the percentage of descrambled TV content is increased to 99.6% which provides acceptable image quality.
C) The third approach, referred to as "signature forgery", is the most dangerous approach because it permits any verifier to forge signatures from only public data. Signature forgery proceeds as follows: